package com.algrithom.tree.binarytree;

import java.util.List;
import java.util.Stack;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 剑指 Offer 07. 重建二叉树
 */
class Solution13 {
    
    public static void main(String[] args){
        //    int[] preorder = new int[] {3, 9, 20, 15, 7};
        int[] preorder = new int[]{1,2,3,4};
        //    int[] inorder = new int[] {9, 3, 15, 20, 7};
        int[] inorder = new int[]{3,2,1,4};
        Solution13 solution13 = new Solution13();
        TreeNode<Integer> root = solution13.buildTree(preorder,inorder);
        List<Integer> result = TreeOperUtil.preRecScan(root);
        System.out.println(result);
    }
    
    public TreeNode<Integer> buildTree(int[] preorder,int[] inorder){
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode<Integer> root = new TreeNode<>(preorder[0]);
        int length = preorder.length;
        Stack<TreeNode<Integer>> stack = new Stack<>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < length; i++) {
            int preorderVal = preorder[i];
            TreeNode<Integer> node = stack.peek();
            if (node.getValue() != inorder[inorderIndex]) {
                node.setLeftChild(new TreeNode<>(preorderVal));
                stack.push(node.getLeftChild());
            } else {
                while (!stack.isEmpty() && stack.peek().getValue() == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.setRightChild(new TreeNode<>(preorderVal));
                stack.push(node.getRightChild());
            }
        }
        return root;
    }
}
